import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lily
 * Date: 2024-09-21
 * Time: 11:28
 */
public class subarray_Sum {
    public static int subarraySum(int[] nums, int k) {
        
        int ret=0;
        int n=nums.length;
        int[] dp=new int[n+1];
        for (int i = 1; i < n+1; i++) {
//            if (nums[i-1]==k){
//                ret++;
//            }
            dp[i]=dp[i-1]+nums[i-1];
        }
        for (int i = 1; i < n+1; i++) {
            for (int j = i-1; j >= 0 ; j--) {
               int tmp=dp[i]-dp[j];
               if (tmp==k){
                   ret++;
               }
            }
        }
        return ret;
        
    }

    public static int sub(int[] nums,int k){
        Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
        hash.put(0, 1);
        int sum = 0, ret = 0;
        for(int x : nums)
        {
            sum += x; // 计算当前位置的前缀和
            ret += hash.getOrDefault(sum - k, 0); // 统计结果
            hash.put(sum, hash.getOrDefault(sum, 0) + 1); // 把当前的前缀和丢到哈
        }
        return ret;
    }


    public static void main(String[] args) {
        int[] arr={1,3,2,2,4};
        System.out.println(sub(arr, 4));
    }
}
